package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//
// Created by ✎﹏ℳ๓独赏☆独醉 on 2024/4/29.
// 
public class 四数之和 {
    public static void main(String[] args) {
        int[] nums = {1000000000,1000000000,1000000000,1000000000};
        int target = -294967296;
        System.out.println(fourSum(nums,target));
    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 4) return res;
        Arrays.sort(nums);
        for (int i = 0; i <= nums.length-4; i++) {
            long t1 = target - nums[i];
//            System.out.println(t1);
            for (int j = i + 1; j <= nums.length-3; j++) {
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;//去除重复
                }
                if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                    break;//若从i出发，距离最小的四个数（即最小的四个数）相加就已经比目标值大，那么后续的也无法满足条件，一定会大于目标值
                }
                if ((long) nums[i] + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1] < target) {
                    continue;//若从数组尾部出发的连续三个数（即最大的四个数）相加还比目标值小，那么后续的也无法满足条件，一定会小于目标值
                }
                long t2 = t1 - nums[j];
//                System.out.println(t2);
                int left = j + 1,right = nums.length-1;
                while (left < right){
                    long temp = nums[left] + nums[right];
//                    System.out.println(temp);
                    if(temp == t2){
                        if(!res.contains(Arrays.asList(nums[i],nums[j],nums[left],nums[right]))){
                            res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        }
                        right--;
                        while (right > left && nums[right] == nums[right + 1])right--;
                        left++;
                        while (left < right && nums[left] == nums[left-1])left++;
                    }else if(temp > t2){
                        right--;
                        while (right > left && nums[right] == nums[right + 1])right--;
                    }else {
                        left++;
                        while (left < right && nums[left] == nums[left-1])left++;
                    }
                }
            }
        }
        return res;
    }
}
